package singlelinkedlist;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2023-12-19
 * Time: 11:12
 */
// 1、无头单向非循环链表实现
public class SingleLinkedList {

    //头指针是链表相关的数据信息，与结点无关
    ListNode head = null;

    //头插法
    public void addFirst(int data){
        //每次增加结点，都要先实例化这个结点，再进行链表操作
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }


    //尾插法
    public void addLast(int data) {
        //实例化要插入的结点
        ListNode node = new ListNode(data);
        //如果链表为空:
        if(head == null) {
            this.head = node;
        }
        ListNode cur = this.head;
        //遍历链表到当前的尾部:
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }


    private void checkPos(int pos) {
        //如果链表是一个非法的范围
        if(pos < 0 || pos > size()) {
            throw new IndexException("您输入了一个违规的位置信息!");
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        //先判断位置信息是否正确:
        checkPos(index);
        //如果输入的位置是0，即在头节点插入:
        if(index == 0) {
            addFirst(data);
        }
        //如果输入的结点是尾端:
        if(index == size()) {
            addLast(data);
        }

        ListNode node = new ListNode(data);
        ListNode cur = head;
        //遍历到需要插入的位置之前:
        for (int i = 0; i < index -1 ; i++) {
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }


    //删除第一次出现关键字为key的节点

    /**
     * 1.由于要删除，只能通过cur.next来判断是否等于key
     * 2.由于使用的.next来判断是否相同，所以头结点无法判断，需要单独判断(在最后)
     * 3.头结点需要最后判断，如果头结点先判断，则会产生一个新的需要单独判断的头结点
     * 4.如果头结点为Null，需要直接return null;
     * @param key
     */
    public void remove(int key) {
        if(head == null) {
            return;
        }
        ListNode cur = head;
        if(head.val == key) {
            head = head.next;
        }
        while(cur.next != null) {
            if(cur.next.val == key) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
            return;
        }

    }


    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        ListNode cur = head;
        while(cur.next != null) {
            if(cur.next.val == key) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        //上述代码无法判断头节点是否为要删除的元素:
        if(head.val == key) {
            head = head.next;
        }
    }


    //得到单链表的长度
    public int size() {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur =cur.next;
            len++;
        }
        return len;
    }
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear() {
        head = null;
    }
}